package day190822;

/**
 * @author LI DUO
 * @version 1.0
 * @date 2019/8/22 下午 04:24
 */
public class MaxProfit {

    public int maxProfit(int[] prices) {
        if (prices.length == 0) {
            return 0;
        }
        int maxPro = 0;
        int cur = prices[0];
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > cur) {
                maxPro += prices[i] - cur;
            }
            cur = prices[i];
        }
        return maxPro;
    }

    /**
     * sell[i]=max(sell[i-1],buy[i-1]+prices[i]);
     * buy[i]=max(buy[i-1],cooldown[i-1]-prices[i]);
     * cooldown[i]=max(cooldown[i-1],max(sell[i-1],buy[i-1])).
     *
     * @param prices
     * @return
     */
    public int maxProfitDP(int[] prices) {
        if (prices.length == 0) {
            return 0;
        }
        int[] sell = new int[prices.length];
        int[] buy = new int[prices.length];
        int[] coolDown = new int[prices.length];
        buy[0] -= prices[0];
        for (int i = 1; i < prices.length; i++) {
            sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);
            buy[i] = Math.max(buy[i - 1], coolDown[i - 1] - prices[i]);
            coolDown[i] = Math.max(coolDown[i - 1], Math.max(sell[i - 1], buy[i - 1]));
        }
        return sell[prices.length - 1];
    }


    /**
     * dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
     * dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])
     * 解释：第 i 天选择 buy 的时候，要从 i-2 的状态转移，而不是 i-1 。
     * @param prices
     * @return
     */
    public int maxProfitDP2(int[] prices) {
        int n = prices.length;
        int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
        // 代表 dp[i-2][0]
        int dp_pre_0 = 0;
        for (int i = 0; i < n; i++) {
            int temp = dp_i_0;
            dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
            dp_i_1 = Math.max(dp_i_1, dp_pre_0 - prices[i]);
            dp_pre_0 = temp;
        }
        return dp_i_0;
    }
}
